{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Missing Non-negative Integer After Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findSmallestInteger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #执行操作后的最大 MEX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个整数 <code>value</code> 。</p>\n",
    "\n",
    "<p>在一步操作中，你可以对 <code>nums</code> 中的任一元素加上或减去 <code>value</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果 <code>nums = [1,2,3]</code> 且 <code>value = 2</code> ，你可以选择 <code>nums[0]</code> 减去 <code>value</code> ，得到 <code>nums = [-1,2,3]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[-1,2,3]</code> 的 MEX 是 <code>0</code> ，而 <code>[1,0,3]</code> 的 MEX 是 <code>2</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回在执行上述操作 <strong>任意次</strong> 后，<code>nums</code><em> </em>的最大 MEX <em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,-10,7,13,6,8], value = 5\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>执行下述操作可以得到这一结果：\n",
    "- nums[1] 加上 value 两次，nums = [1,<em><strong>0</strong></em>,7,13,6,8]\n",
    "- nums[2] 减去 value 一次，nums = [1,0,<em><strong>2</strong></em>,13,6,8]\n",
    "- nums[3] 减去 value 两次，nums = [1,0,2,<em><strong>3</strong></em>,6,8]\n",
    "nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,-10,7,13,6,8], value = 7\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>执行下述操作可以得到这一结果：\n",
    "- nums[2] 减去 value 一次，nums = [1,-10,<em><strong>0</strong></em>,13,6,8]\n",
    "nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length, value &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-missing-non-negative-integer-after-operations](https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-missing-non-negative-integer-after-operations](https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-10,7,13,6,8]\\n5', '[1,-10,7,13,6,8]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        vst = [0] * value\n",
    "        for x in nums:\n",
    "            vst[x % value] += 1\n",
    "        cnt = 0\n",
    "        while True:\n",
    "            for i in range(value):\n",
    "                if vst[i] == 0:\n",
    "                    return i + cnt\n",
    "                vst[i] -= 1\n",
    "            cnt += value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnts = [0] * value\n",
    "\n",
    "        for num in nums:\n",
    "            cnts[num%value] += 1\n",
    "            # if num >= 0:\n",
    "            #     cnts[num%value] += 1\n",
    "            # else:\n",
    "            #     if (num%value) == 0:\n",
    "            #         cnts[0] += 1\n",
    "            #     else:\n",
    "            #         cnts[value + (num%value)] += 1\n",
    "        \n",
    "        minCnt = min(cnts)\n",
    "\n",
    "        for i in range(value):\n",
    "            if cnts[i] == minCnt:\n",
    "                return cnts[i] * value + i\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        n=len(nums)\n",
    "        temp=[0]*value\n",
    "        for i in nums:\n",
    "            temp[i%value]+=1\n",
    "        ans=0\n",
    "        # print(temp)\n",
    "        while True:\n",
    "            if temp[ans%value]:\n",
    "                temp[ans%value]-=1\n",
    "                ans+=1\n",
    "            else:return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = [0] * value\n",
    "        for x in nums: cnt[x % value] += 1\n",
    "        i = cnt.index(min(cnt))\n",
    "        return i + cnt[i] * value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "\n",
    "        n, dict = len(nums), [0] * value\n",
    "        for num in nums:\n",
    "            dict[num % value] += 1\n",
    "        for i in range(n):\n",
    "            if dict[i % value] == 0:\n",
    "                return i \n",
    "            dict[i % value] -= 1\n",
    "        return n \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        remainderCounter = [0] * value\n",
    "        for x in nums: \n",
    "            remainderCounter[x % value] += 1\n",
    "        i = remainderCounter.index(min(remainderCounter))\n",
    "        return i + remainderCounter[i] * value\n",
    "# 作者：_G_\n",
    "# 链接：https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations/solutions/2191054/qiu-yu-tan-xin-ji-suan-2598-zhi-xing-cao-fcwo/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mod = [0]*value\n",
    "        for i in nums:\n",
    "            mod[i % value] += 1\n",
    "        mi = min(mod)\n",
    "        idx = mod.index(mi)\n",
    "        return mi * value + idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        a = [0] * value\n",
    "        for x in nums:\n",
    "            a[x % value] += 1\n",
    "        print(a)\n",
    "        mn = min(a)\n",
    "        if all(x == mn for x in a): return len(nums)\n",
    "        \n",
    "        idx = a.index(mn)\n",
    "        print(idx)\n",
    "        return mn * value + idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = [0] * value\n",
    "        for x in nums: cnt[x % value] += 1\n",
    "        i = cnt.index(min(cnt))\n",
    "        return i + cnt[i] * value\n",
    "\n",
    "# 作者：_G_\n",
    "# 链接：https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations/solutions/2191054/qiu-yu-tan-xin-ji-suan-2598-zhi-xing-cao-fcwo/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        counter = [0] * value\n",
    "        for num in nums:\n",
    "            counter[num % value] += 1\n",
    "        curr = 0\n",
    "        while True:\n",
    "            if counter[curr % value] > 0:\n",
    "                counter[curr % value] -= 1\n",
    "                curr += 1\n",
    "            else:\n",
    "                return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        counter = [0] * value\n",
    "        for x in nums: \n",
    "            counter[x % value] += 1\n",
    "        i = counter.index(min(counter))\n",
    "        return i + counter[i] * value\n",
    "\n",
    "# 作者：_G_\n",
    "# 链接：https://leetcode.cn/problems/smallest-missing-non-negative-integer-after-operations/solutions/2191054/qiu-yu-tan-xin-ji-suan-2598-zhi-xing-cao-fcwo/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        a=[0]*value\n",
    "        for i in nums:\n",
    "            a[i%value]+=1\n",
    "        m=min(a)\n",
    "        return a.index(m)+m*value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        f = [0] * value\n",
    "        for x in nums:\n",
    "            f[x % value] += 1\n",
    "        m = min(f)\n",
    "        ans = m * value\n",
    "        for x in f:\n",
    "            if x == m:\n",
    "                break\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt=[0]*value\n",
    "        for num in nums:\n",
    "            cnt[num%value]+=1\n",
    "        MEX=0\n",
    "        while cnt[MEX%value]!=0:\n",
    "            cnt[MEX%value]-=1\n",
    "            MEX+=1\n",
    "        return MEX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mp = [0] * value\n",
    "        for n in nums:\n",
    "            mp[n%value] += 1\n",
    "        max_val = min(mp)\n",
    "        for i,m in enumerate(mp):\n",
    "            if m==max_val:\n",
    "                return m*value + i \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        dp = [0] * value\n",
    "        for nu in nums:\n",
    "            dp[nu % value] += 1\n",
    "        m = min(dp)\n",
    "        for i in range(value):\n",
    "            if dp[i] == m:\n",
    "                return m * value + i\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        a = [0] * value\n",
    "        for x in nums:\n",
    "            a[x % value] += 1\n",
    "        i = a.index(min(a))\n",
    "        return value * a[i] + i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:         \n",
    "        \n",
    "        times = [-1] * value\n",
    "        # 最大可能也就是len(nums)或value了\n",
    "        # time[i]记录模==i的当前出现了几次？\n",
    "        # 0,1,2,3,4 缺5\n",
    "        for i in range(len(nums)):\n",
    "            #先尽量每个往小的填充 # 找到第一个 是False的 mod value==i\n",
    "            current_val = nums[i]            \n",
    "            # print(i,current_val%value)\n",
    "            times[current_val%value]+=1\n",
    "        \n",
    "        print(times)\n",
    "        # 找最小次数在哪一位，就是缺失的值 完整的一轮 以及完成了多少轮次到的-1\n",
    "        \n",
    "        min_times_idx = times.index(min(times))\n",
    "        MEX = min_times_idx + value*(times[min_times_idx]+1)#完成几轮\n",
    "        return MEX\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "\n",
    "        cnt=[0]*value\n",
    "\n",
    "        for num in nums:\n",
    "            cnt[num%value]+=1\n",
    "        i= cnt.index(min(cnt))\n",
    "        print(cnt)\n",
    "        return i+cnt[i]*value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        q = [x % value for x in nums]\n",
    "        n = [0] * value\n",
    "        for i in q:\n",
    "            n[i] += 1\n",
    "        min = n[0]\n",
    "        index = 0\n",
    "        for i in range(len(n)):\n",
    "            if n[i] < min:\n",
    "                min = n[i]\n",
    "                index = i\n",
    "        return (min) * value+index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        n=len(nums)\n",
    "        tmp = [nums[i]%value for i in range(n)]\n",
    "\n",
    "        #print(tmp)\n",
    "        ans = [0]*n\n",
    "        for num in tmp:\n",
    "            if num>=n:continue\n",
    "            ans[num]+=1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if ans[i]==0:return i\n",
    "            if ans[i]>1:\n",
    "                tmp = ans[i]-1\n",
    "                if i+value<n:\n",
    "                    ans[i+value]+=tmp\n",
    "                ans[i]=1\n",
    "        \n",
    "            \n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:         \n",
    "        number_list = [False]*len(nums)\n",
    "        times = [-1] * value\n",
    "        # 最大可能也就是len(nums)或value了\n",
    "        # time[i]记录模==i的当前出现了几次？\n",
    "        # 0,1,2,3,4 缺5\n",
    "        for i in range(len(nums)):\n",
    "            #先尽量每个往小的填充 # 找到第一个 是False的 mod value==i\n",
    "            current_val = nums[i]            \n",
    "            # print(i,current_val%value)\n",
    "            times[current_val%value]+=1\n",
    "        \n",
    "        print(times)\n",
    "        # 找最小次数在哪一位，就是缺失的值 完整的一轮 以及完成了多少轮次到的-1\n",
    "        \n",
    "        min_times_idx = times.index(min(times))\n",
    "        MEX = min_times_idx + value*(times[min_times_idx]+1)#完成几轮\n",
    "        return MEX\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, a: List[int], v: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        s=[0 for i in range(v)]\n",
    "        n=len(a)\n",
    "        for i in a:\n",
    "            s[i%v]+=1\n",
    "        i=0\n",
    "        # print(s,n)\n",
    "        while n>0:\n",
    "            if s[i%v]>0:\n",
    "                s[i%v]-=1\n",
    "                n-=1\n",
    "                i+=1\n",
    "            else:\n",
    "                return i\n",
    "            # print(i,s,n)\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        arr = [[] for _ in range(value)]\n",
    "        nums.sort()\n",
    "        for x in nums:\n",
    "            mod = x % value\n",
    "            arr[mod].append(x)\n",
    "\n",
    "        for i in range(len(nums) + 1):\n",
    "            j = i // value\n",
    "            m = i % value\n",
    "            if len(arr[m]) <= j:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, arr: List[int], x: int) -> int:\n",
    "        # dict = {}\n",
    "        # # 防止bug\n",
    "        # for i in range(x):\n",
    "        #     dict[i] = 1\n",
    "        # for elem in arr:\n",
    "        #     dict[elem%x] += 1\n",
    "        # mex = -x\n",
    "\n",
    "        # 上面可替换为\n",
    "        # from collections import Counter \n",
    "        dict = Counter(elem % x for elem in arr)\n",
    "        mex = 0\n",
    "\n",
    "        while (dict[mex%x]):\n",
    "            dict[mex%x] -= 1\n",
    "            mex += 1\n",
    "        return mex\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter()\n",
    "        for num in nums:\n",
    "            cnt[num % value] += 1\n",
    "        for i in range(1000000000000):\n",
    "            if cnt[i % value] != 0:\n",
    "                cnt[i% value] -= 1\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, A: List[int], k: int) -> int:\n",
    "        c = Counter(x % k for x in A)\n",
    "        mex = min(range(k), key=c.__getitem__)\n",
    "        return c[mex] * k + mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter(x + value * ceil(abs(x) / value) if x < 0 else x % value for x in nums)\n",
    "        # print(cnt)\n",
    "        i = 0\n",
    "        while cnt[i % value]:\n",
    "            cnt[i % value] -= 1\n",
    "            i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        map = {}\n",
    "        for n in nums:\n",
    "            a = n % value\n",
    "            if a not in map:\n",
    "                map[a] = 1\n",
    "            else:\n",
    "                map[a] += 1\n",
    "        \n",
    "        print(map)\n",
    "        mex = 0\n",
    "        while mex % value in map and map[mex % value] != 0:\n",
    "            map[mex % value] -= 1\n",
    "            mex += 1\n",
    "        return mex\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter(x % value for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % value]:\n",
    "            cnt[mex % value] -= 1\n",
    "            mex += 1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        hashmap = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            hashmap[((num % value) + value) % value] += 1\n",
    "        mex = 0\n",
    "        while hashmap[mex % value] >= 1:\n",
    "            hashmap[mex % value] -= 1\n",
    "            mex += 1\n",
    "        return mex\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter(x % value for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % value]:\n",
    "            cnt[mex % value] -= 1\n",
    "            mex += 1\n",
    "        return mex\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter((x % value + value) % value for x in nums)\n",
    "        i = 0\n",
    "        while cnt[i % value]:\n",
    "            cnt[i % value] -= 1\n",
    "            i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mp = Counter(n%value for n in nums)\n",
    "        ans = 0\n",
    "        while True:\n",
    "            if mp[ans%value]!=0:\n",
    "                mp[ans%value] -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        # 数组中缺失的最小非负整数\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1 \n",
    "            mex += 1\n",
    "        return mex "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mp = Counter(n%value for n in nums)\n",
    "        ans = 0\n",
    "        while True:\n",
    "            if mp[ans%value]!=0:\n",
    "                mp[ans%value] -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter(x % value for x in nums)\n",
    "\n",
    "        x = 0\n",
    "        while cnt[x % value]:\n",
    "            cnt[x % value] -= 1\n",
    "            x += 1\n",
    "\n",
    "        return x\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            r = num % value\n",
    "            if(r < 0):\n",
    "                r += value\n",
    "            if(r not in mapping):\n",
    "                mapping[r] = 1\n",
    "            else:\n",
    "                mapping[r] += 1\n",
    "        v = 0\n",
    "        while((v % value) in mapping):\n",
    "            mapping[v % value] -= 1\n",
    "            if(mapping[v % value] == 0):\n",
    "                del mapping[v % value]\n",
    "            v += 1\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter()\n",
    "        for i in range(len(nums)):\n",
    "            cnt[nums[i] % value] += 1\n",
    "        \n",
    "        for i in range(1000000000000):\n",
    "            if cnt[i % value] != 0:\n",
    "                cnt[i % value] -= 1\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mp = dict()\n",
    "        for num in nums:\n",
    "            mod = num % value\n",
    "            mp[mod] = mp.get(mod, 0) + 1\n",
    "        \n",
    "        mincnt, mod = inf, 0\n",
    "        for i in range(value):\n",
    "            cnt = mp.get(i, 0)\n",
    "            if mincnt > cnt:\n",
    "                mincnt, mod = cnt, i\n",
    "        \n",
    "        return mincnt * value + mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        n = len(nums)\n",
    "        value = value if value > 0 else -1 * value \n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            if nums[i] < 0:\n",
    "                nums[i] = nums[i] % value + value \n",
    "            nums[i] %= value \n",
    "            cnt[nums[i]] += 1\n",
    "        #print(cnt)\n",
    "        i = 0\n",
    "        while True:\n",
    "            if cnt[i%value] == 0:\n",
    "                return i \n",
    "            else:\n",
    "                cnt[i%value] -= 1\n",
    "            i += 1\n",
    "        #return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        # using modular\n",
    "        cnt = Counter(x % value for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % value]:\n",
    "            cnt[mex % value] -= 1\n",
    "            mex += 1\n",
    "        return mex\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            r = num % value\n",
    "            if(r < 0):\n",
    "                r += value\n",
    "            if(r not in mapping):\n",
    "                mapping[r] = 1\n",
    "            else:\n",
    "                mapping[r] += 1\n",
    "        v = 0\n",
    "        while((v % value) in mapping):\n",
    "            mapping[v % value] -= 1\n",
    "            if(mapping[v % value] == 0):\n",
    "                del mapping[v % value]\n",
    "            v += 1\n",
    "        return v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        help = collections.Counter(x%value for x in nums)\n",
    "        i = 0\n",
    "        while i<=len(nums):\n",
    "            if (i%value) not in help or help[i%value]==0:\n",
    "                return i\n",
    "            else:\n",
    "                help[i%value]-=1\n",
    "                i+=1\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter(x%value for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex%value]:\n",
    "            cnt[mex%value]-=1 \n",
    "            mex+=1\n",
    "        return mex\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mp = Counter(n%value for n in nums)\n",
    "        ans = 0\n",
    "        while True:\n",
    "            if mp[ans%value]!=0:\n",
    "                mp[ans%value] -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        help = collections.Counter(x%value for x in nums)\n",
    "        i = 0\n",
    "        while i<len(nums):\n",
    "            if (i%value) not in help or help[i%value]==0:\n",
    "                return i\n",
    "            else:\n",
    "                help[i%value]-=1\n",
    "                i+=1\n",
    "        return len(nums)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        n=len(nums)\n",
    "        cnt=Counter(x%value for x in nums)\n",
    "        mex=0\n",
    "        while cnt[mex%value]:\n",
    "            cnt[mex%value]-=1\n",
    "            mex+=1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, arr: List[int], x: int) -> int:\n",
    "        # dict = {}\n",
    "        # # 防止bug\n",
    "        # for i in range(x):\n",
    "        #     dict[i] = 1\n",
    "        # for elem in arr:\n",
    "        #     dict[elem%x] += 1\n",
    "        # mex = -x\n",
    "\n",
    "        # 上面可替换为\n",
    "        from collections import Counter \n",
    "        dict = Counter(elem % x for elem in arr)\n",
    "        mex = 0\n",
    "\n",
    "        while (dict[mex%x]):\n",
    "            dict[mex%x] -= 1\n",
    "            mex += 1\n",
    "        return mex\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "任意操作\n",
    "\n",
    "--->取余\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt=Counter()\n",
    "        for tn in nums:    \n",
    "            cnt[tn%value]+=1\n",
    "        # print(cnt)\n",
    "        c=0\n",
    "        while(cnt[c%value]):  ##最大情况为 len(nums) < 10**5\n",
    "            cnt[c%value]-=1\n",
    "            c+=1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        mp = Counter(n%value for n in nums)\n",
    "        ans = 0\n",
    "        while True:\n",
    "            if mp[ans%value]!=0:\n",
    "                mp[ans%value] -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        '''\n",
    "        考虑把0,1,2,3,4,5...n-1凑出来\n",
    "        如果凑不出来那么就是答案\n",
    "        那么用谁去凑呢?\n",
    "        每个num 可以凑出k*val+num\n",
    "        num%val=(k*val+num)%val=(k+num%v)%v\n",
    "        0,num%val==0\n",
    "        1,num%val==1\n",
    "        已经想到n^2的做法了，看能不能优化\n",
    "        那么首先把0-val-1凑出来，如果有多的，可以凑第二轮，\n",
    "        那么直接统计0-val-1的出现次数，最小值*val+下标\n",
    "        6578\n",
    "        '''\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            nums[i]%=value\n",
    "        cnt=Counter(nums)\n",
    "        mn=inf\n",
    "        idx=0\n",
    "        for i in range(value):\n",
    "            if cnt[i]<mn:\n",
    "                mn=cnt[i]\n",
    "                idx=i\n",
    "        return mn*value+idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt = Counter(num%value for num in nums)\n",
    "        ans = 0\n",
    "        while cnt[ans%value]:\n",
    "            cnt[ans%value] -= 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        # Step 1: 计算每个模值的计数\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        \n",
    "        # Step 2: 从0开始，寻找MEX\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        \n",
    "        return mex\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for n in nums:\n",
    "            dic[n % value] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            k = i%value\n",
    "            if k in dic and dic[k] > 0:\n",
    "                dic[k] -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        cnt=Counter(x%value for x in nums)\n",
    "        mex=0\n",
    "        while cnt[mex%value]:\n",
    "            cnt[mex%value]-=1\n",
    "            mex+=1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, arr: List[int], x: int) -> int:\n",
    "        dict = {}\n",
    "        # 防止bug\n",
    "        for i in range(x):\n",
    "            dict[i] = 1\n",
    "        for elem in arr:\n",
    "            dict[elem%x] += 1\n",
    "        mex = -x\n",
    "\n",
    "        # 上面可替换为\n",
    "        # from collections import Counter \n",
    "        # dict = Counter(elem % x for elem in arr)\n",
    "        # mex = 0\n",
    "\n",
    "        while (dict[mex%x]):\n",
    "            dict[mex%x] -= 1\n",
    "            mex += 1\n",
    "        return mex\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i%value not in dic.keys():\n",
    "                dic[i%value] = 1\n",
    "            else:\n",
    "                dic[i%value] += 1\n",
    "        for i in range(1000000000000):\n",
    "            if i % value not in dic.keys() or dic[i%value] == 0:\n",
    "                return i\n",
    "            else:\n",
    "                dic[i % value] -= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        d = {}\n",
    "        for i in range(value):\n",
    "            d[i] = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            d[num%value] += 1\n",
    "        for i in range(len(nums)+1):\n",
    "            remainder = i%value\n",
    "            if d[remainder] == 0:\n",
    "                return i\n",
    "            else:\n",
    "                d[remainder] -= 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        c=collections.Counter()\n",
    "        for i in range(value):\n",
    "            c[i]=0\n",
    "        for n in nums:\n",
    "            if n<0:\n",
    "                n-=(n//value)*value\n",
    "            tp=n%value\n",
    "            c[tp]+=1\n",
    "        loop=float(\"inf\")\n",
    "        now=0\n",
    "        #print(c)\n",
    "        for i in range(value-1,-1,-1):\n",
    "            if c[i]<loop:\n",
    "                loop=c[i]\n",
    "                now=i\n",
    "            if c[i]==loop:\n",
    "                now=i\n",
    "        return loop*value+now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        a,b = divmod(13, 7)\n",
    "        ans = Counter()\n",
    "        for i in nums:\n",
    "            a, b = divmod(i, value)\n",
    "            ans[b] +=1\n",
    "        mex = 0\n",
    "        while ans[mex % value]:\n",
    "            ans[mex % value] -=1\n",
    "            mex +=1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], m: int) -> int:\n",
    "        cnt = Counter(x % m for x in nums)\n",
    "        mex = 0\n",
    "        while cnt[mex % m]:\n",
    "            cnt[mex % m] -= 1\n",
    "            mex += 1\n",
    "        return mex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "\n",
    "\n",
    "        d = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            d[num%value] += 1\n",
    "        \n",
    "        now = 0\n",
    "        while True:\n",
    "            if d[now%value] == 0:\n",
    "                return now\n",
    "            d[now%value] -= 1\n",
    "            now += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "\n",
    "\n",
    "        d = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            d[num%value] += 1\n",
    "        \n",
    "        now = 0\n",
    "        while True:\n",
    "            if d[now%value] == 0:\n",
    "                return now\n",
    "            d[now%value] -= 1\n",
    "            now += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        n = len(nums)\n",
    "        value = value if value > 0 else -1 * value \n",
    "        cnt = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            if nums[i] < 0:\n",
    "                nums[i] = nums[i] % value + value \n",
    "            nums[i] %= value \n",
    "            cnt[nums[i]] += 1\n",
    "        print(cnt)\n",
    "        i = 0\n",
    "        while True:\n",
    "            if cnt[i%value] == 0:\n",
    "                return i \n",
    "            else:\n",
    "                cnt[i%value] -= 1\n",
    "            i += 1\n",
    "        #return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        n = len(nums) \n",
    "        for i in range(n) : \n",
    "            nums[i] = nums[i] % value \n",
    "        print(nums)\n",
    "        cnt = Counter(nums) \n",
    "        for i in count(0) : \n",
    "            x = i % value \n",
    "            if x in cnt.keys() : \n",
    "                cnt[x] -= 1 \n",
    "                if cnt[x] == 0 : \n",
    "                    del cnt[x] \n",
    "            else : \n",
    "                return i "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        MEX = 0\n",
    "        mod_hash = Counter([x%value for x in nums])\n",
    "        while True:\n",
    "            if MEX%value in mod_hash and mod_hash[MEX%value] > 0:\n",
    "                mod_hash[MEX%value] = mod_hash[MEX%value] - 1\n",
    "                MEX = MEX + 1\n",
    "            else:\n",
    "                return MEX\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findSmallestInteger(self, nums: List[int], value: int) -> int:\n",
    "        lst = []\n",
    "        for num in nums:\n",
    "            lst.append(num % value)\n",
    "        c = collections.Counter(lst)\n",
    "        x = min(c.values())\n",
    "        for i in range(value):\n",
    "            if c[i]==0:\n",
    "                return i\n",
    "        for i in range(value):\n",
    "            if c[i]==x:\n",
    "                return x*value+i\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
